/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/01
 */
package CodingTest.AC20190301;

import java.util.List;

/**
 * 题目描述：给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

 数学表达式如下:

 如果存在这样的 i, j, k,  且满足 0 ≤ i < j < k ≤ n-1，
 使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

 思路：原地算法复杂度，想到使用二元序列组贪心算法，刚开始使用min = middle = nums[0]；但始终想不到怎么定义
 第一次的二个min和middle，网上设min和middle为最大数很巧妙，因为求该序列组是递增的，所以如过设middle = max = nums[0]，
 可能走得通，未验证，以后再想
 */
public class increasingTriplet {
    public boolean increasingTriplet(int[] nums) {
        int min = Integer.MAX_VALUE;
        int middle = Integer.MAX_VALUE;
        for(int i =0;i<nums.length;i++){
            if(nums[i] >middle){
                return true;
            }else if (min<nums[i]&&nums[i]<=middle){
                middle = nums[i];
            }else{
                min = nums[i];
            }
        }
        return false;

    }

    public static void main(String[] args) {
        int[] nums = {5,1,5,5,2,5,4};
        increasingTriplet ic = new increasingTriplet();
        System.out.println(ic.increasingTriplet(nums));
    }
}
